package com.liezh.tree;

/**
 * 卡塔兰数，n个结点的二叉搜索树总共能构成几棵树？
 * @author liezh
 * @date 2021-4-8
 */
public class CatalanNumber {

    public static void main(String[] args) {

        CatalanNumber catalanNumber = new CatalanNumber();
        catalanNumber.genTables(5);
        int result = catalanNumber.catalanNumberPd(5);
        System.out.println(result);
    }

    private int[] tables;

    private void genTables(int n) {
        tables = new int[n+1];
        tables[0]= tables[1] = 1;
    }

    private int catalanNumberPd(int n) {
        if (tables[n] >= 1) return tables[n];
        tables[n] = 0;
        for (int i = 1 ; i <= n ; i++) {
            tables[n] += catalanNumberPd(i-1) * catalanNumberPd(n-i);
        }
        return tables[n];
    }

    private int catalanNumber(int n) {
        if (n == 0) {
            return 1;
        }
        int count = 0;
        for (int i = 1 ; i <= n ; i++) {
            count += catalanNumber(i-1) * catalanNumber(n-i);
        }
        return count;
    }
}
